package org.example.StacksAndQueues;

import java.util.ArrayDeque;

public class Maximum_sliding_window_value {
    public static void main(String[] args) {
        //滑动窗口最大值

        //给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
        //返回 滑动窗口中的最大值 。
        int[] nums = {1,3,1,2,0,5};
        for (int i : maxSlidingWindow(nums, 3)) {
            System.out.print(i + " ");
        }
    }
public static class myque{
        ArrayDeque<Integer> que;
        public myque(){
            que = new ArrayDeque<>();
        }
        public void pop(int value){
            if (!que.isEmpty() && value == que.peekLast()) que.pollLast();
        }
        public void push(int value){
            while(!que.isEmpty() && value > que.peekFirst()){
                que.removeFirst();
            }
            que.push(value);
        }
        public int getmax(){
            return que.peekLast();
        }

}
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1){
            return nums;
        }
        int[] arr = new int[nums.length - k + 1];
        myque myque = new myque();
        for (int i = 0; i < k; i++) {
            myque.push(nums[i]);
        }
        int num = 0;
        arr[num++] = myque.getmax();
        for (int i = 0,j = k; j < nums.length; i++,j++) {
            myque.pop(nums[i]);
            myque.push(nums[j]);
            arr[num++] = myque.getmax();
        }
        return arr;
    }
    //暴力破解超出时间限制
    public static int[] maxSlidingWindow1(int[] nums, int k) {
        if (nums.length == 1){
            return nums;
        }
        int[] arr = new int[nums.length - k + 1];
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < k; i++) {
            deque.addLast(nums[i]);
        }
        int max = max(deque);
        int num = 0;
        arr[num] = max;
        for (int i = k; i < nums.length; i++) {
            Integer poll = deque.poll();
            deque.add(nums[i]);
            if (poll!=max && max>nums[i]){
                arr[++num] = max;
            }else {
                max = max(deque);
                arr[++num] = max;
            }
        }
        return arr;
    }

    public static int max(ArrayDeque<Integer> deque) {
        int max = deque.peek();
        for (Integer integer : deque) {
            if (max < integer) max = integer;
        }
        return max;
    }
}
